#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElements(int* nums, int numsSize, int* returnSize)
{
	*returnSize = numsSize;
	if (!nums || numsSize <= 0)
		return NULL;
	int* ans = malloc(sizeof(int) * numsSize); // init ans
	memset(ans, -1, sizeof(int) * numsSize);
	const int len = numsSize * 2 - 1;
	int* stack = malloc(sizeof(int) * len); // position records
	int top = 0;    // stack top pointer
	for (int i = 0; i < numsSize * 2 - 1; i++)
	{
		const idx = i % numsSize; // array pos
		while (top > 0 && nums[stack[top - 1]] < nums[idx])
		{
			ans[stack[top - 1]] = nums[idx];
			top--;
		}
		stack[top++] = idx;
	}
	free(stack);
	return ans;
}

int main()
{
	int* returnSize = malloc(sizeof(int));
	int nums[] = { 1, 2, 1 };
	int numsSize = sizeof(nums) / sizeof(*nums);
	int* ans = nextGreaterElements(nums, numsSize, returnSize);
	printf("size = %d : ", *returnSize);
	for (int i = 0; i < *returnSize; i++)
	{
		printf("%d", ans[i]);
	}

	int num1[] = { 6, 2, 6, 5, 1, 2 };
	int numsSize1 = sizeof(num1) / sizeof(*num1);
	int* ans1 = nextGreaterElements(num1, numsSize1, returnSize);
	printf("\nsize = %d : ", *returnSize);
	for (int i = 0; i < *returnSize; i++)
	{
		printf("%d", ans1[i]);
	}

	return 0;
}
